#pragma once

#include "bintree.hpp"

template <typename T>
BinNodePosi(T) BinNode<T>::insertAsLC(T const& e)
{
  return lc = new BinNode(e, this);
}

template <typename T>
BinNodePosi(T) BinNode<T>::insertAsRC(T const& e)
{
  return rc = new BinNode(e, this);
}

///
/// the next item of traverse In
///
template <typename T>
BinNodePosi(T) BinNode<T>::succ()
{
  BinNodePosi(T) s = this;
  if (rc)
  {
    s = rc;
    while (HasLChild(*s)) s = s->lc;
  }
  else
  {
    while (IsRChild(*s)) s = s->parent;
    s = s->parent;
  }

  return s;
}

template <typename T>
template <typename VST>
void BinNode<T>::travLevel(VST& visit)
{
  std::queue<BinNodePosi(T)> q;
  q.push(this);
  while (!q.empty())
  {
    BinNodePosi(T) node = q.pop();
    visit(node->data);
    if (HasLChild(*node)) q.push(node->lc);
    if (HasRChild(*node)) q.push(node->rc);
  }
}

template <typename T, typename VST>
void visitAlongLeftBranch(BinNodePosi(T) x, VST& visit, std::stack<BinNodePosi(T)> S)
{
  while (x)
  {
    //visit(x->data);
    printf("%d", x->data);
    if (HasRChild(*x))
      S.push(x->rc);
    x = x->lc;
  }
}

template <typename T, typename VST>
void travPre_R(BinNodePosi(T) x, VST& visit)
{
  std::stack<BinNodePosi(T)> S;
  while (true) {
    visitAlongLeftBranch(x, visit, S);
    if (S.empty()) break;
    x = S.top();
    S.pop();
  }
}

template <typename T, typename VST>
void travPre_I1(BinNodePosi(T) x, VST& visit)
{
  std::stack<BinNodePosi(T)> S;
  while (true) {
    visitAlongLeftBranch(x, visit, S);
    if (S.empty()) break;
    x = S.top();
    S.pop();
  }
}

template <typename T, typename VST>
void visitAlongLeftBranch(BinNodePosi(T) x, std::stack<BinNodePosi(T)> S)
{
  while (x)
  {
    S.push_back(x);
    x = x->lc;
  }
}

template <typename T, typename VST>
void travIn_I1(BinNodePosi(T) x, VST& visit)
{
  std::stack<BinNodePosi(T)> S;
  while (true) {
    visitAlongLeftBranch(x, S);
    if (S.empty()) break;
    x = S.pop();
    visit(x->data);
    x = x->rc;
  }
}

template <typename T, typename VST>
void travIn_I2(BinNodePosi(T) x, VST& visit)
{
  std::stack<BinNodePosi(T)> S;
  while (true) {
    if (x)
    {
      S.push(x);
      x = x->lc;
    }
    else if (!S.empty())
    {
      x = S.pop();
      visit(x->data);
      x = x->rc;
    }
    else
      break;
  }
}

template <typename T, typename VST>
void travIn_I3(BinNodePosi(T) x, VST& visit)
{
  bool backtrack = false;
  while (true) {
    if (!backtrack && HasLChild(*x))
      x = x->lc;
    else
    {
      visit(x->data);
      if (HasRChild(*x))
      {
        x = x->rc;
        backtrack = false;
      }
      else
      {
        if (!(x = x->succ())) break;
        backtrack = true;
      }
    }
  }
}

template <typename T>
template <typename VST>
void BinNode<T>::travPre(VST& visit)
{
  switch (rand() % 2)
  {
  case 1:
    travPre_I1(this, visit); break;
  default:
    travPre_R(this, visit); break;
  }
}

template <typename T>
template <typename VST>
void BinNode<T>::travIn(VST& visit)
{
  switch (rand() % 5)
  {
  case 1:
    travIn_I1(this, visit); break;
  case 2:
    travIn_I2(this, visit); break;
  case 3:
    travIn_I3(this, visit); break;
  case 4:
    travIn_I4(this, visit); break;
  default:
    travIn_R(this, visit); break;
  }
}

template <typename T>
template <typename VST>
void BinNode<T>::travPost(VST& visit)
{
  switch (rand() % 5)
  {
  case 1:
    travPost_I1(this, visit); break;
  default:
    travIn_R(this, visit); break;
  }
}

template <typename T>
static void gotoHLVFL(std::stack<BinNodePosi(T)>& S) {
  while (BinNodePosi(T) x = S.top())
  {
    if (HasLChild(*x))
    {
      if (HasRChild(*x))
      {
        S.push(x->rc);
      }
      S.push(x->lc);
    }
    else
    {
      S.push(x->rc);
    }
  }
  S.pop();
}

template <typename T, typename VST>
void travPost_I1(BinNodePosi(T) x, VST& visit)
{
  std::stack<BinNodePosi(T)> S;
  if (x) S.push(x);
  while (!S.empty())
  {
    if (S.top() != x->parent)
      gotoHLVFL(S);
    x = S.pop();
    visit(x->data);
  }
}

/****************************************************************************/

template<typename T>
template<typename iter>
BinNodePosi(T) BinTree<T>::buildTreeFromPreAndIn(iter pre_first, iter pre_last, iter in_first, iter in_last) {
  if (distance(pre_first, pre_last) != distance(in_first, in_last)) return nullptr;
  if (pre_first == pre_last) return nullptr;
  if (in_first == in_last) return nullptr;
  auto node = new BinNode<T>(*pre_first);

  auto inRootPos = find(in_first, in_last, *pre_first);
  auto inLeftSize = distance(in_first, inRootPos);
  auto preLeftLast = next(pre_first, inLeftSize + 1);

  node->lc = buildTreeFromPreAndIn(next(pre_first), preLeftLast, in_first, next(in_first, inLeftSize));
  node->rc = buildTreeFromPreAndIn(preLeftLast, pre_last, next(inRootPos), in_last);
  return node;
}

template<typename T>
template<typename BidiIt>
BinNodePosi(T) BinTree<T>::buildTreeFromInAndPost(BidiIt in_first, BidiIt in_last, BidiIt post_first, BidiIt post_last) {
  if (distance(post_first, post_last) != distance(in_first, in_last)) return nullptr;
  if (in_first == in_last) return nullptr;
  if (post_first == post_last) return nullptr;
  auto node = new BinNode<T>(*prev(post_last));

  auto inRootPos = find(in_first, in_last, *post_last);
  auto inLeftSize = distance(in_first, inRootPos);
  auto postLeftLast = next(post_first, inLeftSize);

  node->lc = buildTreeFromInAndPost(in_first, inRootPos, post_first, postLeftLast);
  node->rc = buildTreeFromInAndPost(next(inRootPos), in_last, postLeftLast, prev(post_last));
  return node;
}

template <typename T>
BinNodePosi(T) BinTree<T>::preAndInOrderCreate(std::vector<T> pre, std::vector<T> in)
{
  _root = buildTreeFromPreAndIn(pre.begin(), pre.end(), in.begin(), in.end());
  return _root;
}

template <typename T>
BinNodePosi(T) BinTree<T>::inAndPostOrderCreate(std::vector<T> in, std::vector<T> post)
{
  _root = buildTreeFromInAndPost(in.begin(), in.end(), post.begin(), post.end());
  return _root;
}

template <typename T>
void BinTree<T>::updateHeightAndAbove(BinNode<T>* x)
{
  while (x) {
    updateHeight(x);
    x = x->parent;
  }
}

template <typename T>
int BinTree<T>::updateHeight(BinNode<T>* x)
{
  return x->height = 1 + std::max(stature(x->lc), stature(x->rc));
}

template <typename T>
BinNodePosi(T) BinTree<T>::insertAsRoot(T const& e)
{
  _size = 1; return _root = new BinNode<T>(e);
}

template <typename T>
BinNodePosi(T) BinTree<T>::insertAsLC(BinNodePosi(T) x, T const& e)
{
  _size++; x->insertAsLC(e); updateHeightAndAbove(x); return x->lc;
}

template <typename T>
BinNodePosi(T) BinTree<T>::insertAsRC(BinNodePosi(T) x, T const& e)
{
  _size++; x->insertAsRC(e); updateHeightAndAbove(x); return x->rc;
}

template <typename T>
BinNodePosi(T) BinTree<T>::attachAsLC(BinNodePosi(T) x, BinTree<T>*& s)
{
  if (x->lc == s->_root) x->lc->parent = x;
  _size += s->_size;
  updateHeightAndAbove(x);
  s->_root = nullptr; s->_size = 0; release(s); s = nullptr; return x;
}

template <typename T>
BinNodePosi(T) BinTree<T>::attachAsRC(BinNodePosi(T) x, BinTree<T>*& s)
{
  if (x->rc == s->_root) x->rc->parent = x;
  _size += s->_size;
  updateHeightAndAbove(x);
  s->_root = nullptr; s->_size = 0; release(s); s = nullptr; return x;
}

template <typename T>
BinTree<T>* BinTree<T>::secede(BinNodePosi(T) x) {
  FromParentTo(*x) = NULL;
  updateHeightAndAbove(x->parent);
  BinTree<T>* s = new BinTree<T>;
  s->_root = x;
  x->parent = NULL;
  s->_size = x->size(); _size -= s->_size;
  return s;
}

template <typename T>
int BinTree<T>::remove(BinNode<T>* x)
{
  FromParentTo(*x) = NULL;
  updateHeight(x->parent);
  int n = removeAt(x); _size -= n;
  return n;
}